class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def countPairs(self, root, distance):
        """
        :type root: TreeNode
        :type distance: int
        :rtype: int
        """
        self.ans = 0
        if distance < 2:
            return 0

        def dfs(node):
            if node.left:
                if node.right:
                    p1 = dfs(node.left)
                    p2 = dfs(node.right)
                    for i in range(distance - 1):
                        if i == 0:
                            self.ans += p1[i] * p2[distance - i - 2]
                        else:
                            self.ans += (p1[i] - p1[i - 1]) * p2[distance - i - 2]
                    p = [0] * distance
                    for i in range(1, distance):
                        p[i] = p1[i - 1] + p2[i - 1]
                else:
                    p = dfs(node.left)
                    for i in range(distance - 1, 0, -1):
                        p[i] = p[i - 1]
                    p[0] = 0
            else:
                if node.right:
                    p = dfs(node.right)
                    for i in range(distance - 1, 0, -1):
                        p[i] = p[i - 1]
                    p[0] = 0
                else:
                    p = [1] * distance
            return p

        dfs(root)
        return self.ans
